using System;
using System.Collections.Generic;
namespace GraphSpace
{
	public class Dial : IPQ
	{
		private List<int>[] buckets;
		int currentBucket;
		private Dictionary<int, Knoten> elements;
		private int c;
		private int deleteMinCounter;

		public Dial ()
		{
			this.c = 0;
		}

		public void init (int C)
		{
			this.c = C;
			buckets = new List<int>[c + 2];
			for (int i = 0; i < c + 2; i++)
			{
				buckets[i] = new List<int> ();
			}
			elements = new Dictionary<int, Knoten> ();
			currentBucket = 0;
			deleteMinCounter = 0;
		}

		public Dial (int C)
		{
			this.c = C;
			buckets = new List<int>[c + 2];
			for (int i = 0; i < c + 2; i++)
			{
				buckets[i] = new List<int> ();
			}
			elements = new Dictionary<int, Knoten> ();
			currentBucket = 0;
			deleteMinCounter = 0;
		}

		public Knoten extractHead ()
		{
			//Console.Write("D.eH : ");
			// Prüfe, ob tempMinBucket noch Elemente besitzt
			if (buckets[currentBucket].Count > 0)
			{
				//Console.WriteLine("Bucket "+elements[tempMinBucket[0]].bucket+" Id "+elements[tempMinBucket[0]].id);
				Knoten item = elements[buckets[currentBucket][0]];
				for (int j = 1; j < buckets[currentBucket].Count; j++)
				{
					elements[buckets[currentBucket][j]].position--;
				}
				buckets[currentBucket].RemoveAt (0);
				return item;
			}

			
			else
			{
				currentBucket = (currentBucket + 1) % (c + 1);
				return extractHead ();
				
			}
		}

		public bool insert (Knoten item)
		{
			elements.Add (item.id, item);
			// Dictionary Id -> Dial_Knoten
			int d;
			
			int cast = (Int32)(item.distance);
			d = cast % (c + 1);
			buckets[d].Add (item.id);
			// im Unendlich-Bucket an letzter Stelle einfügen
			item.bucket = d;
			// Zeiger auf Bucket setzen
			item.position = (buckets[d].Count - 1);
			// Zeiger auf Position im Bucket setzen
			return true;
		}

		public bool decreaseKey (Knoten item, double key)
		{
			//Console.Write ("D dK " + item.id);
			//	try
			//	{
			// Zuerst im alten Bucket entfernen und Zeiger der übrigen Elemente im Bucket aktuallisieren
			deleteMinCounter++;
			buckets[item.bucket].RemoveAt (item.position);
			for (int i = item.position; i < buckets[item.bucket].Count; i++)
			{
				int position = elements[buckets[item.bucket][i]].position - 1;
				elements[buckets[item.bucket][i]].position = position;
			}
			//Console.Write(" von "+item.bucket+"."+item.position + " nach ");
			
			// Anschliessend den Knoten im neunen Bucket einfügen und seine Zeiger anpassen
			int d = ((int)key) % (c + 1);
			buckets[d].Add (item.id);
			item.bucket = d;
			item.position = (buckets[d].Count - 1);
			
			//Console.WriteLine(item.bucket + "." +item.position + "("+key+" = "+d+")");
			
			return true;
			//	}
			//	catch(Exception e)
			//	{
			//		Console.WriteLine("Fehler in Dial::decreaseKey("+id+", "+key+")"+e.ToString());
			//		return false;
			//	}
		}

		public int getDeleteMinCounter ()
		{
			return deleteMinCounter;
		}

		public double getMinDistance ()
		{
			if (buckets[currentBucket].Count > 0)
			{
				//Console.WriteLine("Bucket "+elements[tempMinBucket[0]].bucket+" Id "+elements[tempMinBucket[0]].id);
				return elements[buckets[currentBucket][0]].distance;
			}
			else
			{
				currentBucket = (currentBucket + 1) % (c + 1);
				return getMinDistance ();
			}
		}

		public bool isEmpty ()
		{
			for (int i = 0; i < c + 2; i++)
			{
				if (buckets[i].Count > 0)
					return false;
			}
			return true;
		}

		public void show ()
		{
			// Alle normalen Buckets
			for (int i = 0; i < c + 1; i++)
			{
				Console.WriteLine ("\t" + i + ". Bucket");
				foreach (int j in buckets[i])
				{
					Console.WriteLine ("\t\t" + elements[j].ToString ());
				}
			}
			// unendlicher Bucket
			Console.WriteLine ("\tunendliches Bucket");
			foreach (int j in buckets[c + 1])
			{
				Console.WriteLine ("\t\t" + elements[j].ToString ());
			}
		}
	}
}

